1. Field of the Invention
The present invention relates to a system, a method, and a program for selecting routes such as traffic routes.
2. Description of Related Art
Car navigation systems have a function which searches for and displays traffic routes. The algorithm in this process, for example, treats intersections as nodes and road segments as edges, and searches for the shortest route in a weighted graph in which the lengths of routes are weighted.
However, at this time, a large number of automobiles have car navigation systems that are used to simultaneously search for routes, and each automobile independently determines the shortest route. When this causes an overlap of traffic routes for a plurality of automobiles, the frequency of use of particular routes or edges increases, and congestion occurs in some of these routes. At this time, as shown in FIG. 1, the times for each route are believed to increase rapidly as traffic volume increases.
In automobiles, traffic information provided by the Vehicle Information and Communication System (VICS) is referenced so that the car navigation system can calculate an alternate route. However, when a large number of vehicles reference the same traffic information, similar alternate routes are eventually selected and this causes further congestion as shown in FIG. 2.
Therefore, there is a need for a central server to take into account the occurrence of congestion due to a concentration of vehicles and, as shown in FIG. 3, perform many-to-many routing to alleviate congestion. In other words, there is a possibility of reducing required times if congestion can be mutually avoided. However, the calculations performed in many-to-many routing usually experience difficulties, and it is difficult to come up with a solution in a reasonable amount of time.
A system is disclosed in Japanese Patent Publication No. 2001-331564 for realizing an effective plan by calculating routes for each means of transport in a transportation plan using a means optimized for the necessary precision and calculation time of each plan. This system, which has at least an input/output device, a processor and a storage device, and which creates a distribution plan, comprises: a base information registration step for inputting position information for a base such as a factory, a relay base, and a supplier, a transportation service information registration step for inputting transportation delivery information including bases that each transportation service visits and load quantities, a condition registration step for inputting target information including the necessary accuracy and limit time of a transportation plan, an algorithm selection step for selecting an algorithm used for route preparation, a route preparation step for preparing a route for a delivery service from this information, and an output step for outputting the result.
Japanese Patent Publication No. 2004-12312 discloses a route searching device comprising a first searching means for searching for a minimum cost route along which the parameter accompanying the route becomes the minimum among the parameters accompanying the routes from a starting point to a destination, a weighting means for weighing the parameter of each road section constituting a first shortest route, and an area limiting means for finding a specific map area as a limited area based on the calculated data of the first searching means. This device also comprises a second searching means for searching for a route only in the limited area found by means of the area limiting means by regarding the area as an object to be searched. The time required for a subsequent search is shortened by limiting the search range by utilizing information obtained during the previous search.
Japanese Patent Publication No. 2009-19932 discloses a route search system for searching for a moving route for an autonomous moving body reaching a moving end point from a moving start point, which comprises a region dividing portion for dividing a moving region into a plurality of regions, a plurality of evaluation value calculating portion for calculating an evaluation value of each region, corresponding to the plurality of regions divided by the region dividing part, and a route determining portion for determining the route, based on the evaluation values calculated by the evaluation value calculating parts. The evaluation value calculating portion has an evaluation value processing portion for calculating an evaluation value based on the evaluation value of a region existing nearby and moving cost from a nearby region to its own region. Paragraph 0073 states that “the number of regions indicated as moving start points and moving end points can be applied to the present invention whether it is many-to-one, one-to-many, or many-to-many.
However, none of the prior art literature discloses a technique for obtaining many-to-many route search processing with a reasonable amount of computation, even though a simple solution requires an enormous amount of computation.